package sort;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-14
 * Time: 9:45
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {2, 1, 32, 1, 32, 1, 32, 1, 3};
        quickSortNonR(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 用于交换数组下标的值
     * @param arr
     * @param index1
     * @param index2
     */
    private static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    //一. 递归法

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        //优化处理
        //解决的问题：1. 不断递归，会在栈中不断开辟新空间，若数据过多会出现栈溢出 2. 减少时间复杂度
        //1. 三数取中法
        dealPivot(arr, left, right);
        //2. 在其中使用insertSort排序，减少递归的次数
        if (right - left <= 100) {//当递归的数据到达某个阈值时，直接放弃递归，开始插入排序
            //InsertSort()
            //使用时记得修改insertSort()函数的相关参数，因为left可能不是从0开始的，right可能也不是数组长度
            return;
        }
        int mid = partition2(arr, left, right);
        quickSort(arr, left, mid - 1);
        quickSort(arr, mid + 1, right);
    }

    //1. 挖坑法
    /**
     * 该函数是以left为分割点，将其分为左右小大两部分
     * @param arr
     * @param left
     * @param right
     * @return 返回的是分割点的下标
     */
    private static int partition(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int pivot = arr[left];
        while (l < r) {
            //必须先右开始，否则l可能会为负数，数组会越界
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            arr[l] = arr[r];//初始的arr[left]已经被pivot保存下来，所以不必担心丢失一个数据
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            arr[r] = arr[l];
        }
        //此时的l==r，将该点的值覆盖为pivot
        arr[l] = pivot;
        return l;
    }

    //2. Hoare法
    private static int partition1(int[] arr, int left, int right){
        int l = left;
        int r = right;
        int pivot = arr[left];
        while (l < r) {
            while (l < r && arr[r] >= pivot) {
                r--;
            }
            while (l < r && arr[l] <= pivot) {
                l++;
            }
            swap(arr, l, r);
        }
        swap(arr, l, left);
        return l;
    }

    //3. 前后指针
    public static int partition2(int[] arr, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (arr[left] > arr[cur] && arr[++prev] != arr[cur]) {
                swap(arr, cur, prev);
            }
            cur++;
        }
        swap(arr, left, prev);
        return prev;
    }
    //若数组为[1, 2, 3, 4, 5],则每次都没有左半部分，就只能不断地向右递归（时间复杂度n^2）
    //若每次左右分割的数字都相同，那么时间将大大节省（时间复杂度nlogn）
    //考虑优化
    //三数取中法，（即尽可能的每次二分）
    public static void dealPivot(int[] arr, int left, int right) {
        int mid = left + (right - left) / 2;//避免数字越界int
        //三个数使用升序排，直接冒泡思想
        if (arr[left] > arr[mid]) {
            swap(arr, left, mid);
        }
        if (arr[mid] > arr[right]) {
            swap(arr, mid, right);
        }
        if (arr[left] > arr[mid]) {
            swap(arr, left, mid);
        }
        //因为我使用的是arr[left]为pivot
        swap(arr, left, mid);
    }

    //二. 非递归法
    public static void quickSortNonR(int[] arr, int left, int right) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            if (left >= right) {
                continue;
            }
            //dealPivot(arr,left,right);//同样可使用三数取中法优化
            int mid = partition(arr, left, right);
            //根据栈的性质，注意放的顺序
            stack.push(mid + 1);
            stack.push(right);
            stack.push(left);
            stack.push(mid - 1);
        }
    }

}
